The invention relates generally to convolutional decoders and more particularly to convolutional decoders with forward and backward recursion, such as soft decision output decoders and methods.
Soft decision output decoders, such as maximum a posteriori (MAP) decoders are known for use with convolutional codes to decode symbols that represent transmitted information, such as voice, video, data or other information communicated over wireless communication link. Convolutional decoders with forward and backward recursion are known and sometimes used to decode the constituent recursive convolutional codes used in turbo codes. Such decoders perform recursive decoding which uses soft decision information from one pass of a MAP algorithm as input to a next pass of a MAP algorithm to obtain a best estimate of transmitted information data as determined from decoded symbols. As known in the art, in the MAP algorithm, the forward recursion evaluates the joint probability of the state at time t and the received data through time t. The backward recursion computes the probability of the received data from time t to the end of the frame given the state at time. Hence, the computation of this probability for backward recursion decoders typically starts from an end of a frame. The MAP decoder is described, for example, in an article entitled xe2x80x9cOptimal Decoding of Linear Codes for Minimizing Symbol Error Ratexe2x80x9d by L. R. Bahl et al., published IEEE Transactions on Information Theory, March 1974. One application of this MAP decoder can be found in xe2x80x9cNear Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codesxe2x80x9d,: by C. Berrou et al., Proceedings of ICC ""93, Geneva, Switzerland, pp. 1064-1070, May, 1993, incorporated herein by reference.
For decoding of turbo codes, for example, such as in code division multiple access (CDMA) wireless communication systems, decoding of recursive convolutionally coded information bits requires the determination of the following state in a trellis given a present state, and the input bit, such as a hypothetical information bit. Some decoding algorithms, such as the MAP algorithm, update the trellis in a backward as well as in a forward direction so that it is necessary to determine the next state of the coder (encoder) (the state at time n+1 for forward recursion, and the state at time nxe2x88x921 for backward recursion) given the present state (at n) and the input bit. This operation is typically performed for every state in the trellis and it is therefore important that this process be done in an efficient manner.
Given the current state "sgr"n of the M element shift register, defined as
"sgr"n=("sgr"n0,"sgr"n1, . . . ,"sgr"nMxe2x88x921)
and input bit un, the next state of the forward recursion can easily be calculated by clocking the shift register to give
"sgr"n+1=(un⊕fn,"sgr"n0, . . . ,"sgr"nMxe2x88x922)
where the feedback bit fn is defined as the modulo-2 addition of those shift register elements specified in the feedback polynomial gf. A more difficult problem is finding "sgr"nxe2x88x921, the next state of the backward recursion given "sgr"n and un where,
"sgr"nxe2x88x921=("sgr"nxe2x88x9210,"sgr"nxe2x88x9211, . . . ,"sgr"nxe2x88x921Mxe2x88x921)
One solution is to use a lookup table that provides the next state for each state and input bit. This requires a precomputed 2M+1 by M bit look up table. However, such look up tables utilize scarce memory and require additional complexity to generate the look up tables.
Accordingly, a need exists for a more efficient recursive convolutional decoder that can avoid the use of such a look up table.